LC 373. Find K Pairs with Smallest Sums.md

Posted on | In |

Description

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.

1
2
3
4
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Solution

1
2
3
4
5
Every time when we meet a min/max k problems, we should think about using heap to deal with it.
O(n ^ 2 logk) is very easy to come up with, we should do some optimization.
We know that we just need k pairs in the final result, therefore, we can loop k times, every time, we should
append the minimum pair we can get at present(the top of heap). At the same time, we should use a set to record
and avoid duplication.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        # O(klog(n))
        m, n = len(nums1), len(nums2)
        if m == 0 or n == 0: return []
        res, heap, seen = [], [(nums1[0] + nums2[0], 0, 0)], {(0, 0)}
        for _ in range(k):
            if not heap: return res
            v, i, j = heapq.heappop(heap)
            res.append((nums1[i], nums2[j]))
            if i < m - 1 and (i + 1, j) not in seen:
                seen.add((i + 1, j))
                heapq.heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j))
            if j < n - 1 and (i, j + 1) not in seen:
                seen.add((i, j + 1))
                heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
        return res
Donate comment here